#pragma once
#include<iostream>
using namespace std;
#include<string.h>
#include<assert.h>

#define NUMMAX 10
#define CONSTMAX 100
typedef int WeightType;
typedef char VerterType[50];
struct ArcNode
{
	WeightType info;
	int vexi;
	ArcNode* next;
};
struct VexNode
{
	VerterType vertex;
	ArcNode* firstArc;
};
struct ALGraph
{
	VexNode adjlist[NUMMAX];
	int arcNum;
	int vexNum;
};

void ALGraphCreate(ALGraph& G);
void ALGraphDisp(const ALGraph& G);

void ALGraphDFS(const ALGraph& G);
void ALGraphBFS(const ALGraph& G);
typedef int QDataType;
struct QueueNode
{
	QDataType _data;
	QueueNode* _next;
};
class Queue
{
public:
	Queue()
	{
		_front = _rear = NULL;
		_size = 0;
	}
	void Push(const QDataType& x)
	{
		QueueNode* s = NewNode(x);
		if (_front == NULL)
		{
			_front = _rear = s;
		}
		else
		{
			_rear->_next = s;
			_rear = s;
		}
		_size++;
	}
	int Empty()
	{
		return !(_size);
	}
	void Pop()
	{
		assert(!Empty());
		if (_front == _rear)
		{
			free(_front);
			_front = _rear = NULL;
		}
		else
		{
			QueueNode* next;
			next = _front->_next;
			free(_front);
			_front = next;
		}
		_size--;
	}
	QDataType Front()
	{
		assert(!Empty());
		return _front->_data;
	}

private:
	QueueNode* NewNode(const QDataType& x)
	{
		QueueNode* s = (QueueNode*)malloc(sizeof(QueueNode));
		if (s == NULL)
		{
			perror("malloc fail::");
			return NULL;
		}
		s->_data = x;
		s->_next = NULL;
		return s;
	}

	QueueNode* _front;
	QueueNode* _rear;
	int _size;
};